package design;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author pengfei.hpf
 * @date 2020/4/3
 * @verdion 1.0.0
 *
 * 211. 添加与搜索单词 - 数据结构设计
 * 设计一个支持以下两种操作的数据结构：
 *
 * void addWord(word)
 * bool search(word)
 * search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。
 *
 * 示例:
 *
 * addWord("bad")
 * addWord("dad")
 * addWord("mad")
 * search("pad") -> false
 * search("bad") -> true
 * search(".ad") -> true
 * search("b..") -> true
 * 说明:
 *
 * 你可以假设所有单词都是由小写字母 a-z 组成的。
 */
public class WordDictionary {

    TrieNode root;
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        if(word == null || word.length() == 0){
            return;
        }
        char[] chars = word.toCharArray();
        TrieNode cur = root;
        for(char c: chars){
            TrieNode nextC = cur.add(c);
            cur = nextC;
        }
        cur.isEnd = true;
    }



    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        if(word == null || word.length() == 0){
            return false;
        }
        TrieNode node = root;
        char[] chars = word.toCharArray();
        return dfs(chars, 0, root);
    }

    private boolean dfs(char[] chars, int start, TrieNode node){
        if(start == chars.length - 1){
            if(chars[start] == '.'){
                for(TrieNode r: node.childs){
                    if(r != null && r.isEnd){
                        return true;
                    }
                }
                return false;
            }
            TrieNode r = node.get(chars[start]);
            return r != null && r.isEnd;
        }
        char c = chars[start];
        if(c == '.'){
            for(TrieNode r: node.childs){
                if(r != null && dfs(chars, start + 1, r)){
                    return true;
                }
            }
            return false;
        } else {
            TrieNode n = node.get(c);
            if(n != null){
                return dfs(chars, start + 1, n);
            }
            return false;
        }

    }

    class TrieNode{
        TrieNode[] childs;
        boolean isEnd;
        TrieNode(){
            childs = new TrieNode[26];
        }

        TrieNode add(char c){
            int index = c - 'a';
            TrieNode node = childs[index];
            if(node == null){
                node = new TrieNode();
                childs[index] = node;
            }
            return node;
        }

        TrieNode get(char c){
            int index = c - 'a';
            return childs[index];
        }
    }

}
